582. Kill Process
Medium

You have n processes forming a rooted tree structure. You are given two integer arrays pid and ppid, where pid[i] is the ID of the ith process and ppid[i] is the ID of the ith process's parent process.

Each process has only one parent process but may have multiple children processes. Only one process has ppid[i] = 0, which means this process has no parent process (the root of the tree).

When a process is killed, all of its children processes will also be killed.

Given an integer kill representing the ID of a process you want to kill, return a list of the IDs of the processes that will be killed. You may return the answer in any order.

 

Example 1:

Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5
Output: [5,10]
Explanation: The processes colored in red are the processes that should be killed.

Example 2:

Input: pid = [1], ppid = [0], kill = 1
Output: [1]

 

Constraints:

  • n == pid.length
  • n == ppid.length
  • 1 <= n <= 5 * 104
  • 1 <= pid[i] <= 5 * 104
  • 0 <= ppid[i] <= 5 * 104
  • Only one process has no parent.
  • All the values of pid are unique.
  • kill is guaranteed to be in pid.
Accepted
50,561
Submissions
78,552
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.75 (24 votes)

Premium Video

Video Solution


 

Solution Article


Approach #1 Depth First Search [Time Limit Exceeded]

Algorithm

Since killing a process leads to killing all its children processes, the simplest solution is to traverse over the ppidppid array and find out all the children of the process to be killed. Further, for every child chosen to be killed we recursively make call to the killProcess function now treating this child as the new parent to be killed. In every such call, we again traverse over the ppidppid array now considering the id of the child process, and continue in the same fashion. Further, at every step, for every process chosen to be killed, it is added to the list ll that needs to be returned at the end.

Complexity Analysis

  • Time complexity : O(nn)O(n^n). O(nn)O(n^n) function calls will be made in the worst case

  • Space complexity : O(n)O(n). The depth of the recursion tree can go upto nn.


Approach #2 Tree Simulation [Accepted]

Algorithm

We can view the given process relationships in the form of a tree. We can construct the tree in such a way that every node stores information about its own value as well as the list of all its direct children nodes. Thus, now, once the tree has been generated, we can simply start off by killing the required node, and recursively killing the children of each node encountered rather than traversing over the whole ppidppid array for every node as done in the previous approach.

In order to implement this, we've made use of a NodeNode class which represents a node of a tree. Each node represents a process. Thus, every node stores its own value(Node.valNode.val) and the list of all its direct children(Node.childrenNode.children). We traverse over the whole pidpid array and create nodes for all of them. Then, we traverse over the ppidppid array, and make the parent nodes out of them, and at the same time add all their direct children nodes in their Node.childrenNode.children list. In this way, we convert the given process structure into a tree structure.

Now, that we've obtained the tree structure, we can add the node to be killed to the return list ll. Now, we can directly obtain all the direct children of this node from the tree, and add its direct children to the return list. For every node added to the return list, we repeat the same process of obtaining the children recursively.

Complexity Analysis

  • Time complexity : O(n)O(n). We need to traverse over the ppidppid and pidpid array of size nn once. The getAllChildren function also takes atmost nn time, since no node can be a child of two nodes.

  • Space complexity : O(n)O(n). mapmap of size nn is used.


Approach #3 HashMap + Depth First Search [Accepted]

Algorithm

Instead of making the tree structure, we can directly make use of a data structure which stores a particular process value and the list of its direct children. For this, in the current implementation, we make use of a hashmap mapmap, which stores the data in the form parent:[listofallitsdirectchildren]{parent: [list of all its direct children]}.

Thus, now, by traversing just once over the ppidppid array, and adding the corresponding pidpid values to the children list at the same time, we can obtain a better structure storing the parent-children relationship.

Again, similar to the previous approach, now we can add the process to be killed to the return list, and keep on adding its children to the return list in a recursive manner by obtaining the child information from the structure created previously.

Current
1 / 8
**Complexity Analysis**
  • Time complexity : O(n)O(n). We need to traverse over the ppidppid array of size nn once. The getAllChildren function also takes atmost nn time, since no node can be a child of two nodes.

  • Space complexity : O(n)O(n). mapmap of size nn is used.


Approach #4 HashMap + Breadth First Search [Accepted]:

Algorithm

We can also make use of Breadth First Search to obtain all the children(direct+indirect) of a particular node, once the data structure of the form (process:[listofallitsdirectchildren](process: [list of all its direct children] has been obtained. The process of obtaining the data structure is the same as in the previous approach.

In order to obtain all the child processes to be killed for a particular parent chosen to be killed, we can make use of Breadth First Search. For this, we add the node to be killed to a queuequeue. Then, we remove an element from the front of the queuequeue and add it to the return list. Further, for every element removed from the front of the queue, we add all its direct children(obtained from the data structure created) to the end of the queue. We keep on doing so till the queue becomes empty.

Current
1 / 9

Complexity Analysis

  • Time complexity : O(n)O(n). We need to traverse over the ppidppid array of size nn once. Also, atmost nn additions/removals are done from the queuequeue.

  • Space complexity : O(n)O(n). mapmap of size nn is used.

Report Article Issue

Comments: 28
laotzu's avatar
Read More

I think the time complexity for first approach is n^2, because there is no repetition nodes which are already explored during the search process.

13
Show 4 replies
Reply
Share
Report
cleverKnight's avatar
Read More

I feel like you should also mention that a simple topological sort from the 'kill' node generates the answer - particularly Approach #3 does basically just that.

5
Show 1 reply
Reply
Share
Report
nicksg3395's avatar
Read More

Should be an easy problem

30
Reply
Share
Report
slz250's avatar
Read More

can someone explain why the brute force approach (#1) runtime is O(n^n)?

3
Show 3 replies
Reply
Share
Report
mehakwaliaC's avatar
Read More

The time complexity for the first approach should be O(n^2) or otherwise, I just don't know what I am doing here!

1
Reply
Share
Report
codingWithJaz's avatar
Read More

Easy to understand Python3 Solution using Hashmap and Queue:

def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        children_map = defaultdict(list)
        
        for i in range(len(pid)):
            if ppid[i] != 0:
                children_map[ppid[i]].append(pid[i])
        
        
        queue = [kill]
        res = []
        while queue:
            curr_process = queue.pop()
            res.append(curr_process)
            if curr_process in children_map:
                for p in children_map[curr_process]:
                    queue.append(p)
                children_map[curr_process] = []
        
        return res

1
Reply
Share
Report
Mshubhi's avatar
Read More

List < Integer > l = new ArrayList < > ();
        if (kill == 0)
            return l;
        l.add(kill);
        for (int i = 0; i < ppid.size(); i++)
            if (ppid.get(i) == kill)
                l.addAll(killProcess(pid, ppid, pid.get(i)));
        return l;

This code is wrong as if we are killing 0 then it will return an empty list, but since 0 is the root process, ideally all process should be in the result.

if (kill == 0)
           return l; 

I do not think that this base case is required. The recursion will stop if none of the ppid.get(i) is equal to kill.
Correct version:

 List < Integer > l = new ArrayList < > ();
        l.add(kill);
        for (int i = 0; i < ppid.size(); i++)
            if (ppid.get(i) == kill)
                l.addAll(killProcess(pid, ppid, pid.get(i)));
        return l;

1
Show 1 reply
Reply
Share
Report
anupHack's avatar
Read More

I was also thinking if it can be done like, find the node that needs to be killed. Then mark that with respect to its parent as null, (e.g. in this 5 is the node to be killed so mark 2's left to be null ) but save that tree in a temporary node, say temp. After that just traverse using one of the traversal and add the nodes to be printed in an array or list and print them. How about this?

0
Reply
Share
Report
vinod23's avatar
Read More

@mrvon @aprilyin Sorry there was some problem. We have fixed it. Thanks

0
Reply
Share
Report
mrvon's avatar
Read More

It seems mismatching answer and problem.

0
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/21/2021 09:41Accepted84 ms60.7 MBcpp
06/21/2021 09:38Accepted92 ms60.3 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.